package com.yulan.Array;

import org.junit.Test;

import java.util.ArrayList;
import java.util.List;

/**
 * 78. 子集
 * 输入: nums = [1,2,3]
 * 输出:
 * [
 *   [3],
 *   [1],
 *   [2],
 *   [1,2,3],
 *   [1,3],
 *   [2,3],
 *   [1,2],
 *   []
 * ]
 *
 */
public class LeetCode_78 {

    List<List<Integer>> ans = new ArrayList<>();

    public List<List<Integer>> re_subsets(int[] nums) {
        ans.add(new ArrayList<>());
        for(int num:nums){
            List<List<Integer>> newSubSet = new ArrayList<>();
            for(List<Integer> curr : ans){
                newSubSet.add(new ArrayList<Integer>(curr){{add(num);}});
            }
            for(List<Integer> curr:newSubSet){
                ans.add(curr);
            }
        }
        return ans;
    }

    /**
     * 回溯法
     */
    int n, k;
    public List<List<Integer>> bac_subsets(int[] nums){
        n = nums.length;
        for(k = 0;k < n+1;k++){
            backTrack(0,new ArrayList<>(),nums);
        }
        return ans;
    }


    public void backTrack(int first,ArrayList<Integer> curr, int[] arr){
        if(curr.size() == k){
            ans.add(new ArrayList<>(curr));
        }

        for(int i = first;i<n;i++){
            curr.add(arr[i]);

            backTrack(i+1,curr,arr);

            curr.remove(curr.size()-1);
        }
    }

    /**
     * 位操作
     */
    public List<List<Integer>> subsets(int[] nums) {
        int n = nums.length;
        for(int i = (int)Math.pow(2,n);i<(int)Math.pow(2,n+1);i++){
            String bitMask = Integer.toBinaryString(i).substring(1);

            List<Integer> curr = new ArrayList<>();
            for(int j = 0;j<n;j++){
                if(bitMask.charAt(j) == '1') curr.add(nums[j]);
            }
            ans.add(curr);
        }
        return ans;
    }

    @Test
    public void test(){
        int[] arr = {1,2,3};
        for(List<Integer> list : bac_subsets(arr)){
            System.out.println(list);
        }
    }
}
